package Leetcode.图;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: kirito
 * @Date: 2024/9/7 16:51
 * @Description:
 * 用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
 *
 * 网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
 *
 * 给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，
 * 并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。
 *
 * 示例 1：
 *
 * 输入：n = 4, connections = [[0,1],[0,2],[1,2]]
 * 输出：1
 * 解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。
 * 示例 2：
 *
 * 输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
 * 输出：2
 * 示例 3：
 *
 * 输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
 * 输出：-1
 * 解释：线缆数量不足。
 * 示例 4：
 *
 * 输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
 * 输出：0
 */
public class 连通网络的操作次数 {
    public static void main(String[] args) {
        int[][] con = {
                {0, 1},
                {0, 2},
                {1, 2}
        };
        System.out.println(new 连通网络的操作次数().makeConnected(4, con));
    }
    /**
     * 初次理解题意，最少操作次数，无向图中间至少n-1条边可以保证此图为连通图
     * 如果总边数小于n-1 即不可能凑成连通图  返回-1
     *
     * 找图中的连通分量个数，记为A，多出来的k条线，A-1<=k即可成功
     *
     * 为什么只需要找连通分量即可，因为现在n条边都已经在“各自”的连通分量中连通
     * 每多出一个连通分量，必定存在一个连通分量的边的个数会>n-1
     *      否则：connections.length 就会< n - 1     这个不好描述，自己体会
     *
     * @param n n台计算机
     * @param connections   connections[i] = [a, b] 连接了计算机 a 和 b。
     * @return
     */
    public int makeConnected(int n, int[][] connections) {
        //这里的connections可以理解为一个无向图的矩阵  如果有A-B，那么就会有B-A
        if (connections.length < n - 1) {
            return -1;
        }
        List<Integer>[] edges = new List[n];
        boolean[] visited = new boolean[n];
        //初始化图  邻接表
        for (int i = 0; i < n; ++i) {
            edges[i] = new ArrayList<Integer>();
        }
        for (int[] conn : connections) {
            edges[conn[0]].add(conn[1]);
            edges[conn[1]].add(conn[0]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, edges, visited);
                //dfs一次完成，找到一个连通分量
                ans++;
            }

        }
        //最终找到n个连通分量，就需要n-1次操作使得总体成为一整个连通分量
        return ans - 1;

    }

    private void dfs(int i,  List<Integer>[] edges, boolean[] visited) {
        visited[i] = true;
        for (int vertex : edges[i]) {
            if (!visited[vertex]) {
                dfs(vertex, edges, visited);
            }
        }
    }
}
